package leetCode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @PackageName: leetCode
 * @ClassName: LeetCode844
 * @Author: chen jinxu
 * @Date: 2022/3/2 23:23
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。
 
 */
public class LeetCode844 {
    public static void main(String[] args) {
        String s = "ab#c";
        String t = "ad#c";
        boolean result = backspaceCompare(s, t);
        System.out.println(result);
    }

    public static boolean backspaceCompare(String s, String t) {
        Deque<Character> stackS = new LinkedList<>();
        Deque<Character> stackT = new LinkedList<>();
        stackS = getStack(s, stackS);
        stackT = getStack(t, stackT);
        if (stackT.size() == 0 && stackS.size() == 0) {
            return true;
        }
        if (stackT.size() != stackS.size()) {
            return false;
        }
        while (!stackS.isEmpty() && !stackT.isEmpty()) {
            if (stackT.pop() != stackS.pop()) {
                return false;
            }
        }
        return true;
    }

    static Deque<Character> getStack(String s, Deque<Character> stack) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '#') {
                stack.push(s.charAt(i));
            }
            if (stack.peek() != null && s.charAt(i) == '#') {
                stack.pop();
            }
        }
        return stack;
    }

}
